package com.leetcode.search.dfs;

/**
 * @author Dennis Li
 * @date 2020/10/30 16:27
 */
public class IslandPerimeter_463 {

    private int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    private int res = 0;

    public int islandPerimeter(int[][] grid) {
        int high = grid.length, width = grid[0].length;
        for (int i = 0; i < high; i++) {
            for (int j = 0; j < width; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j, new boolean[high][width]);
                    return res;
                }
            }
        }
        return res;
    }

    private void dfs(int[][] grid, int i, int j, boolean[][] visited) {
        int len = 4;
        visited[i][j] = true;
        for (int[] d : directions) {
            int y = i + d[0], x = j + d[1];
            if (y >= 0 && x >= 0 && y < grid.length && x < grid[0].length && grid[y][x] == 1) {
                len--;
                if (!visited[y][x]) {
                    dfs(grid, y, x, visited);
                }
            }
        }
        res += len;
    }

}
